package leetcode.problems;

/**
 * Created by Administrator on 2018/3/20.
 */
public class _0319test {
    /*Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:
    Any left parenthesis '(' must have a corresponding right parenthesis ')'.
    Any right parenthesis ')' must have a corresponding left parenthesis '('.
    Left parenthesis '(' must go before the corresponding right parenthesis ')'.
        '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
    An empty string is also valid.
    Example 1:
    Input: "()"
    Output: True
    Example 2:
    Input: "(*)"
    Output: True
    Example 3:
    Input: "(*))"
    Output: True
    Note:
    The string size will be in the range [1, 100].

    给定一个字符串，它只包含三种类型的字符：'(', ')'和'*'，写一个函数来检查这个字符串是否有效。我们根据这些规则定义字符串的有效性：
    任何左括号'('必须有相应的右括号')'。
    任何右括号')'必须有相应的左括号'('。
    左括号'('必须在相应的右括号')'之前。
        '*'可以被视为单个右括号')'或“左括号'('或空字符）。
    空字符串也是有效的。
    例1：
    Input: "()"
    Output: True
    Example 2:
    Input: "(*)"
    Output: True
    Example 3:
    Input: "(*))"
    Output: True
    注：
    字符串大小将在范围[ 1, 100 ]。


    public boolean checkValidString(String s) {
        int low = 0;
        int high = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                low++;
                high++;
            } else if (s.charAt(i) == ')') {
                if (low > 0) {
                    low--;
                }
                high--;
            } else {
                if (low > 0) {
                    low--;
                }
                high++;
            }
            if (high < 0) {
                return false;
            }
        }
        return low == 0;
    }*/
}
